package com.example.sort;

public class FibonacciProblem {
    public static int fibonacci(int n) {
        if (n <= 0) {
            return -1;
        }
        //创建备忘录数组
        int[] memo = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            memo[i] = -1;
        }
        return fib(n, memo);
    }

    public static int fib(int n,int [] memo){
        //如果已经求出了fib m)的值直接返回
        if(memo[n] !=-1){
            return memo[n];
        }
        //否则将求出的值保存在memo 备忘录中。
        if(n<= 2){
            memo[n]=1;
        }else{
            memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
        }
        return memo[n];
    }


    public static void main(String[] args) {
        int i= fibonacci(5);
        System.out.println(i);
    }
}
